package com.example.leetcode;

/**
 * 动态规划
 * 打家劫舍2 参考题解
 */
public class Demo0213 {

    //思路一:记录是否包含第一家   k-2包含第一家时 则需要去头再来一遍
    public int rob(int[] nums) {
        int len = nums.length;
        if (len==1){
            return nums[0];
        }
        if (len==2){
            return Math.max(nums[0],nums[1]);
        }
        int fun[] =new int[len];
        int[] flag=new int[len];//记录fun是否包含0（即第一家）
        fun[0]=nums[0];
        flag[0]=1;
        if (nums[0]>nums[1]){
            fun[1]=nums[0];
            flag[1]=1;
        }else {
            fun[1]=nums[1];
            flag[1]=0;
        }
        for (int k = 2; k < len; k++) {
            if (k==len-1){
                if (flag[k-2]==0){
                    //k-2不包含第一家
                    fun[k]=Math.max(fun[k-1],fun[k-2]+nums[k]);
                }else if (flag[k-2]==1){
                    //k-2包含第一家时
//                    fun[k]=Math.max(fun[k-1],fun[k-2]+nums[k]-nums[0]);
                    int f[] =new int[len-1];
                    f[0]=nums[1];
                    f[1]=Math.max(nums[1],nums[2]);
                    for (int i = 2; i < len-1; i++) {
                        f[i]=Math.max(f[i-1],f[i-2]+nums[i+1]);
                    }
                    fun[k]=Math.max(fun[k-1],f[len-2]);
                }
                break;
            }
            if (fun[k-1]>fun[k-2]+nums[k]){
                fun[k]=fun[k-1];
                flag[k]=flag[k-1];
            }else if (fun[k-1]==fun[k-2]+nums[k]){
                fun[k]=fun[k-1];
                flag[k]=flag[k-1]*flag[k-2];
            }else {
                fun[k]=fun[k-2]+nums[k];
                flag[k]=flag[k-2];
            }
        }
        return fun[len-1];
    }

    public int rob1(int[] nums) {
        int len = nums.length;
        if (len==1){
            return nums[0];
        }
        if (len==2){
            return Math.max(nums[0],nums[1]);
        }
        if (len==3){
            return Math.max(nums[0],nums[1]);
        }
        return 0;
    }
}
